package 算法.其他算法;

import java.util.Arrays;
import java.util.HashMap;

public class JZ39数组中出现次数超过一半的数字 {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        return  array[array.length/2];
    }

    //哈希表
    public int MoreThanHalfNum_Solution2(int [] array) {
        //哈希表统计每个数字出现的次数
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        //遍历数组
        for(int i = 0; i < array.length; i++){
            //统计频率
            if(!mp.containsKey(array[i]))
                mp.put(array[i], 1);
            else
                mp.put(array[i], mp.get(array[i]) + 1);
            //一旦有个数大于长度一半的情况即可返回
            if(mp.get(array[i]) > array.length / 2)
                return array[i];
        }
        return  0;
    }
}
